/* This file contains the utility functions for the grid
*
*
*/

#include "sudoku.h"

// Gets the number of bits that are 1
inline int bitCount (unsigned int u)
{
	unsigned int uCount;
	uCount = u 
	- ((u >> 1) & 033333333333) 
	- ((u >> 2) & 011111111111);
	return ((uCount + (uCount >> 3)) & 030707070707) % 63;	
}


// clears the num bit
inline void clrCell (int num, cell * c)
{
	cell mask = 0x1;
	mask = mask << (num - 1);
	mask = ~mask;
	*c = *c & mask;
}

// sets the num bit
inline void setCell (int num, cell * c)
{
	cell mask = 0x1;
	mask = mask << (num - 1);
	*c = mask;
}

/*
* x, y point to a solved cell. This method will remove that number from possibilities of other cells
*
*/
bool unmarkCells (Grid g, int x, int y)
{
	int xi, yi;
	int sx, sy;
	bool progress = FALSE;
	sx = getSubGridX(x);
	sy = getSubGridY(y);

	cell cur = gridIndex(g, x, y);
	cell mask = ~cur;
	
	// Column check
	for (yi = 0; yi < GRID_SIZE; yi++)
	{
		if (yi != y)
		{
			if (gridIndex(g, x, yi) & cur)	// There is a match, so we got to remove
			{
				progress = TRUE;
				gridIndex(g, x, yi) = gridIndex(g, x, yi) & mask;
			}
		}
	}
	
	// Row check
	for (xi = 0; xi < GRID_SIZE; xi++)
	{
		if (xi != x)
		{
			if (gridIndex(g, xi, y) & cur)	// There is a match, so we got to remove
			{
				progress = TRUE;
				gridIndex(g, xi, y) = gridIndex(g, xi, y) & mask;
			}
		}
	}
	
	// Subgrid check
	for (yi = 0; yi < SUB_GRID_SIZE; yi++)
	{
		for (xi = 0; xi < SUB_GRID_SIZE; xi++)
		{
			if (&gridIndex(g, x, y) != &subGridIndex(g, sx, sy, xi, yi))	// Make sure the cells are different
			{
				if ((subGridIndex(g, sx, sy, xi, yi) & cur))
				{
					progress = TRUE;
					subGridIndex(g, sx, sy, xi, yi) = subGridIndex(g, sx, sy, xi, yi) & mask;
				}
			}
		}
	}
	
	return progress;
}

void prtCell (cell c, int type)
{
	int i;
	cell mask = 0x1;
	char bin[GRID_SIZE + 1];
	bin[GRID_SIZE] = '\0';
	for (i = 0; i < GRID_SIZE; i++)
	{
		if (c & mask)
		{
			bin[GRID_SIZE - 1 - i] = '1';
		}
		else
		{
			bin[GRID_SIZE - 1 - i] = '0';
		}
		mask = mask << 1;
	}
	mask = 0x1;
	if (type == 1)
	{
		if (bitCount(c) == 1)
		{
			for (i = 0; i < GRID_SIZE; i++)
			{
				if (c & mask)
				{
					printf("%d ", i+1);
					break;
				}
				mask = mask << 1;
			}
		}
		else
		{
			printf(". ");
		}
	}
	else
	{
		printf ("%s ", bin);
	}
}

Grid newGrid (void)
{
	Grid new = malloc(sizeof(cell) * 81);
	return new;
}

void delGrid (Grid g)
{
	free (g);
}

void populateGrid (char * input, Grid g)
{
	int x, y;
	for (y = 0; y < GRID_SIZE; y++)
	{
		for (x = 0; x < GRID_SIZE; x++)
		{
			// Is the input 1-9? Here, gridIndex is indexing into the input string
			if (((gridIndex(input, x, y) - 48) >= 1) && ((gridIndex(input, x, y)- 48) <= GRID_SIZE))
			{
				setCell(gridIndex(input, x, y) - 48, &gridIndex(g, x, y));
			}
			else
			{
				// Set the cell to all 1s. 
				gridIndex(g , x, y) = (0x1 << 9) - 1;
			}
		}
	}
}

void prtGrid (Grid g, int type)
{
	int x, y;
	int num_solved = 0;
	for (y = 0; y < GRID_SIZE; y++)
	{
		for (x = 0; x < GRID_SIZE; x++)
		{
			prtCell(gridIndex(g, x, y), type);
			if (bitCount(gridIndex(g, x, y)) == 1) num_solved++;
		}
		printf ("\n");
	}
	printf("cells solved: %d\n", num_solved);
}

void prtGridBitcount (Grid g)
{
	int x, y;
	for (y = 0; y < GRID_SIZE; y++)
	{
		for (x = 0; x < GRID_SIZE; x++)
		{
			
			printf("%d ", bitCount(gridIndex(g, x, y)));
		}
		printf ("\n");
	}
}

bool isGridSolved(Grid g)
{
	int x, y;
	for (y = 0; y < GRID_SIZE; y++)
	{
		for (x = 0; x < GRID_SIZE; x++)
		{
			if (bitCount(gridIndex(g, x, y)) != 1)
			{
				return FALSE;
			}
		}
	}
	return TRUE;
}

/*
* Goes through each of the solved cells and removes possiblities from others. 
*/
bool markup(Grid g)
{
	bool progress = TRUE;
	int x, y;
	while (progress)
	{
		progress = FALSE;
		for (y = 0; y < GRID_SIZE; y++)
		{
			for (x = 0; x < GRID_SIZE; x++)
			{
				if (bitCount(gridIndex(g, x, y)) == 1)
				{
					progress |= unmarkCells(g, x, y);
				}
			}
		}
	}
	return isGridSolved(g);
}

cellCoord getLeastPossCell(Grid g)
{
	int x, y, bitCnt;
	int possCnt = GRID_SIZE + 1;	// Init to max
	cellCoord low = {0,0};
	cellCoord bad = {-1,-1};
	bool found = FALSE;
	
	for (y = 0; y < GRID_SIZE; y++)
	{
		for (x = 0; x < GRID_SIZE; x++)
		{
			bitCnt = bitCount(gridIndex(g, x, y)); 	// Avoid multiple calls
			
			if(bitCnt != 1 && possCnt > bitCnt)	// Found a new low
			{
				low.x = x;
				low.y = y;
				possCnt = bitCnt;				
				found = TRUE;
			}
		}
	}
	
	return found ? low : bad;
}
